package top.likeqc.leetcode.editor.cn;

import java.util.Arrays;

/**
 * @see <a
 *     href="https://leetcode.cn/problems/minimum-number-of-taps-to-open-to-water-a-garden">1326.
 *     灌溉花园的最少水龙头数目</a>
 */
public class MinimumNumberOfTapsToOpenToWaterAGarden {
    public static void main(String[] args) {
        Solution solution = new MinimumNumberOfTapsToOpenToWaterAGarden().new Solution();

        solution.minTaps(3, new int[] {0, 0, 0, 0});
    }

    // leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int minTaps(int n, int[] ranges) {
            int[][] intervals = new int[n + 1][];
            for (int i = 0; i <= n; i++) {
                int start = Math.max(0, i - ranges[i]);
                int end = Math.min(n, i + ranges[i]);
                intervals[i] = new int[] {start, end};
            }
            Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
            int[] dp = new int[n + 1];
            Arrays.fill(dp, Integer.MAX_VALUE);
            dp[0] = 0;
            for (int[] interval : intervals) {
                int start = interval[0], end = interval[1];
                if (dp[start] == Integer.MAX_VALUE) {
                    return -1;
                }
                for (int j = start; j <= end; j++) {
                    dp[j] = Math.min(dp[j], dp[start] + 1);
                }
            }
            return dp[n];
        }
    }
    // leetcode submit region end(Prohibit modification and deletion)

}
